package com.fang.offer.linked;

import java.util.ArrayList;
import java.util.Stack;

/**
 * <p>
 * 时间限制：1秒 空间限制：32768K 本题知识点： 链表
 * </p>
 * <p>
 * 题目描述 输入一个链表，从尾到头打印链表每个节点的值。
 * </p>
 * 
 */
public class PrintLisked {

	public static void main(String[] args) {
		ListNode root = new ListNode(1);
		root.next = new ListNode(2);
		root.next.next = new ListNode(3);
		PrintLisked printLisked = new PrintLisked();
		ArrayList<Integer> result2 = printLisked.printListFromTailToHead(null);
		for (Integer integer : result2) {
			System.out.print(integer + "  ");
		}
	}

	ArrayList<Integer> result = new ArrayList<>();

	/**
	 * 递归实现
	 * 
	 * @param listNode
	 * @return
	 */
	public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
		if (listNode == null)
			return result;
		if (listNode.next != null) {
			printListFromTailToHead(listNode.next);
		}
		result.add(listNode.val);
		return result;
	}

	/**
	 * 使用栈来处理
	 * 
	 * @param listNode
	 * @return
	 */
	public ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
		Stack<Integer> stack = new Stack<>();
		while (listNode != null) {
			stack.push(listNode.val);
			listNode = listNode.next;
		}

		ArrayList<Integer> list = new ArrayList<>();
		while (!stack.isEmpty()) {
			list.add(stack.pop());
		}
		return list;
	}
}
